package com.yaoli.niuke;

import com.yaoli.ajob.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by siemens on 5/9/2017.
 */
public class _006_Test {

    public static void main(String[] args) {
        _006_Test test = new _006_Test();

        TreeNode  a = new TreeNode(1);
        TreeNode  b = new TreeNode(2);
        TreeNode  c = new TreeNode(3);

        TreeNode  d = new TreeNode(4);
        TreeNode  e = new TreeNode(5);
        TreeNode  f = new TreeNode(6);
        TreeNode  g = new TreeNode(7);

        TreeNode  h = new TreeNode(8);
        TreeNode  i = new TreeNode(9);

        //          1
        //      2       3
        //  4   5       6   7
        // 8 9

        //          a
        //      b       c
        //d      e     f    g
        // h i
        a.setLeft(b);
        a.setRight(c);

        b.setLeft(d);
        b.setRight(e);

        c.setLeft(f);
        c.setRight(g);

        d.setLeft(h);
        d.setRight(i);

        test.Print(a);
    }
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> rowRes = new ArrayList<Integer>();

        LinkedList<TreeNode> llist = new LinkedList<TreeNode>();

        if(pRoot != null){
            llist.offerFirst(pRoot);
        }else{
            res.add(rowRes);
            return res;
        }

        // last 1
        //              1                   //  1
        //          2       3               // 3 2
        //       4   5      6   7           // 4 5 6 7
        //    9  10 11 12 13 14 15 16       // 16 15 14 13 12 11 10 9

        //
        boolean flag = true;

        while(!llist.isEmpty()){
            int length = llist.size();
            rowRes = new ArrayList<Integer>();
            while(length != 0) {
                TreeNode temp;
                if(flag == true){
                    temp = llist.pollLast();
                    if(temp.left != null){
                        llist.offerFirst(temp.left);
                    }
                    if(temp.right != null){
                        llist.offerFirst(temp.right);
                    }
                }else{
                    temp = llist.pollFirst();
                    if(temp.right != null){
                        llist.offerLast(temp.right);
                    }
                    if(temp.left != null){
                        llist.offerLast(temp.left);
                    }
                }

                rowRes.add(temp.val);
                length --;
            }

            res.add(rowRes);
            if(false == flag){
                flag = true;
            }else{
                flag = false;
            }
        }


        return res;
    }
}
